package sort;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/1 10:47
 */
public class HeapSort {
    /*
     希望 这一次, 手写 堆排, 直接能够真正的掌握 堆这种结构!!
     事件复杂度 nlgn

     */

    /*
    堆排:三个 核心的点:
    ① : heapInsert (从元素 插入点的位置, 向上, 进行 heapInsert )
        - 从下向上 构建堆
        - 数组中,一个一个元素的 insert 构建堆的 代价 O(N * lgN)
    ②: heapify
        - 从上向下 (从元素 所在位置, 向下, 进行 heapify)
        - 给出一个 数组, 可以倒序构建, 以 时间复杂度 O(N) 的代价 建成 堆 结构!
    ③: heapSize (逻辑堆的大小)
        - 这个  参数也非常的 核心!
     */

    // insertSort 一遍过,没难度!
    public static void insertSort(int nums[]){
        for(int i = 1;i < nums.length;i++){
            for(int j = i;j > 0;j--){
                if(nums[j] < nums[j - 1]){
                    swap(nums,j,j - 1);
                }else{
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int nums[] = {2,4,1,0,3,8,3,4,4,4};
//        insertSort(nums);
        heapsort2(nums);
//        heapSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    @Test
    public void test(){
        testRight();
//        System.out.println((0 - 1) / 2);
//        int[] ints = ramdomArray(20, 1000, -1, false);
//        int arr1[] = Arrays.copyOf(ints, ints.length);
//        int arr2[] = Arrays.copyOf(ints, ints.length);
////        Arrays.sort(arr1);
//        heapSort(arr1);
//        Arrays.sort(arr2);
//        System.out.println(Arrays.toString(arr1));
//        System.out.println(Arrays.toString(arr2));
//        System.out.println(Arrays.toString(ints));
    }


    /*
     这样实现的 堆排 ，没有任何的问题！
     */
    public static void heapSort(int nums[]){
        // build a  max heap
        for(int i = 0;i < nums.length;i++){
            heapInsert(nums,i);
        }

        int heapSize = nums.length; // 维护的 堆的大小
        while(heapSize > 0){
            swap(nums,0,--heapSize);
            heapify(nums,0,heapSize);
        }

    }



    public static void heapsort2(int nums[]){
        for (int i = 0; i < nums.length; i++) {
            heapInsert2(nums,i);
        }
        int heapSize = nums.length;
//        swap(nums,0,heapSize - 1);
        while(heapSize > 0){
            swap(nums,0,--heapSize);
            heapfiy2(nums,0,heapSize);
//            heapify(nums,0,heapSize);
        }



    }


    public static void heapInsert2(int nums[],int index){ // 表示从哪个位置开始 heapinsert
        // heapInsert 是从下向上  index  - 1  >>  1 表示头节点的位置
        while(nums[index] > nums[(index - 1) /2]){
            swap(nums,index,(index - 1)/ 2);
            index = (index - 1) / 2;
        }

    }

    public static void heapfiy2(int nums[], int index,int heapSize){ // 表示从哪个位置 开始下沉 , 堆排序一般 这个 index = 0
        int l = index * 2 + 1;
        while(l < heapSize){
            int max = l + 1 < heapSize && nums[l + 1] > nums[l] ? l + 1 : l;

            if(nums[max] <= nums[index]){
                break;
            }

            swap(nums,max,index);
            index=  max;
            l = index * 2 + 1;

        }

    }



    /**
     *
     * @param nums
     * @param index  表示 从哪个位置 开始 heapInsert
     *
     */
    public static void heapInsert(int nums[], int index){
        /*
         这里不要用位 运算， 0 - 1 >> 1  = -1 ,这真的是没想到的一个点!
         */
        while(nums[index] > nums[(index - 1)  / 2]){
            swap(nums,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }

    }

    /**
     *
     * @param nums
     * @param index 表示 从哪个 位置 开始 heapify
     * @param heapSize 表示的 维护的 堆的 范围
     */
    public static void heapify(int nums[], int index, int heapSize){
        int left = index * 2 + 1;
        while(left < heapSize){
            int maxIndex = left + 1 < heapSize && nums[left] < nums[left + 1] ? left + 1 : left;
            if(nums[index] > nums[maxIndex]){
                break; // 说明 已经往下走不动了！
            }
            // can down
            swap(nums,index,maxIndex);
            /*
              这里 是个 坑点， 一定要 把 index 也进行变化， 否则会出问题的
             */
            index = maxIndex;
            left = index * 2 + 1;
        }
    }

    public static void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }





    /**
     * 首先生成 随机数组的函数！
     *
     * @param arraySize 数组的大小（根据 题目的 不同， 也可能是 一个数组的  最大长度， 随机生成 数组的 长度 在 1 ~  arraySize 之间）
     * @param max       数组中元素的最大值
     * @param min       一个指标， 如果 min = 0， 代表 数组中的元素，>=0 ，min = 1， 代表 全是正数  min = -1 ，可正 ke 负 ， 可为 0
     * @param fix       如果 fix = true 代表， 数组的长度 固定， 反之， 数组的长度 不固定
     * @return 一个 生成的随机的数组(长度可以随机， 也可以 固定， 看具体题目的要求)
     */
    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)); // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 10000; // 自己写！
        int arraySize = 3000;
        int max = 100000;
        int min = -1;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            // 你的方法
            insertSort(arr1);
//            heapSort(arr2);
            Arrays.sort(arr2);
            if(!Arrays.equals(arr1,arr2)){
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                System.out.println(Arrays.toString(ints));
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }








}

class Singleton{

    private Singleton (){}


    private static class SingletonHolder{
        private  static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton  getInstance(){
        return SingletonHolder.INSTANCE;
    }

}

enum SingletonOne{
    INSTANCE();
    public int a ;


}